package leetcode_core.leetcode_4;

import java.util.HashMap;
import java.util.Map;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年11月18日 8:59
 */
public class FindTargetSumWays {
    private HashMap<String,Integer> memo = new HashMap<>();
    private int dp(int[] nums,int i,int target,int sum,int n){
        if(i == n){
            //产生一种解法
            if(sum == target){
                return 1;
            }
            return 0;
        }
        String key = i+","+sum;
        if(memo.get(key)!=null){
            return memo.get(key);
        }
        //递归回溯
        int result = dp(nums, i+1, target, sum+nums[i], n)+dp(nums,i+1,target,sum-nums[i],n);
        memo.put(key,result);
        return result;
    }
    public int findTargetSumWays(int[] nums, int target) {
        return dp(nums,0,target,0,nums.length);
    }
}
